package leetcode.weekly.week342;

import java.util.HashMap;
import java.util.Map;

//Solution4Test
public class Solution4 {

	public int minOperations(int[] nums) {
		int ans = Integer.MAX_VALUE;
		Map<Integer, Integer> map = new HashMap<>();
		map.put(nums[0], 0);
		Map<Integer, Integer> cnt = new HashMap<>();
		for (int i = 1; i < nums.length; i++) {
			int a = nums[i];
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				int b = entry.getKey(), j = entry.getValue();
				if (gcd(a, b) == 1) {
					int t1 = map.getOrDefault(a, 0);
					int t2 = map.getOrDefault(b, 0);
					ans = Math.min(ans, Math.max(t1, t2) + 1);
				}
			}
			Map<Integer, Integer> tmp = new HashMap<>();
			cnt.put(a, 0);
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				int b = entry.getKey(), j = entry.getValue();
				tmp.put(b, j);
			}
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				int b = entry.getKey(), j = entry.getValue();
				int g = gcd(a, b);
				tmp.put(gcd(a, b), i);
				if (cnt.containsKey(g)) {
					int t1 = map.getOrDefault(a, 0);
					int t2 = map.getOrDefault(b, 0);
					int t = Math.max(t1, t2) + 1;
				}
			}
			map = tmp;
		}
		System.out.println(ans);
		return ans + nums.length - 1;
	}

	public int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}
